import java.util.Arrays;

public class SolutionInterview17_15 {
    public String longestWord(String[] words) {
        Arrays.sort(words,(a,b)->a.length()==b.length()?a.compareTo(b):b.length()-a.length());
        for (int i=0;i<words.length;i++){
            if (dfs(words[i],words,i+1)){
                return words[i];
            }
        }
        return "";
    }

    private boolean dfs(String word, String[] words, int k) {
        if (word.equals("")){
            return true;
        }
        for (int i=k;i<words.length;i++){
            if (word.startsWith(words[i])){
                if (dfs(word.substring(words[i].length()),words,k)){
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionInterview17_15().longestWord(new String[]{"cat","banana","dog","nana","walk","walker","dogwalker"}));
    }
}
